package top.guoziyang.mydb.backend.vm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import top.guoziyang.mydb.common.Error;

/**
 * 维护了一个依赖等待图，以进行死锁检测
 */
public class LockTable {
    
    private Map<Long, List<Long>> x2u;  // 某个XID已经获得的资源的UID列表
    private Map<Long, Long> u2x;        // UID被某个XID持有
    private Map<Long, List<Long>> wait; // 正在等待UID的XID列表
    private Map<Long, Lock> waitLock;   // 正在等待资源的XID的锁
    private Map<Long, Long> waitU;      // XID正在等待的UID
    private Lock lock;

    public LockTable() {
        x2u = new HashMap<>();
        u2x = new HashMap<>();
        wait = new HashMap<>();
        waitLock = new HashMap<>();
        waitU = new HashMap<>();
        lock = new ReentrantLock();
    }


    /**
     * 在每次出现等待的情况时，就尝试向图中增加一条边，并进行死锁检测。如果检测到死锁，就撤销这条边，不允许添加，并撤销该事务
     * 不需要等待则返回null，否则返回锁对象
     */
    public Lock add(long xid, long uid) throws Exception {
        lock.lock();
        try {
            // x2u表示某个XID已经获得的资源的UID列表，这里是判断xid中是否已经有uid这个资源了
            // 如果当前xid已经持有该uid
            if(isInList(x2u, xid, uid)) {
                return null;
            }
            // 如果uid这个资源还没有被任何xid持有
            if(!u2x.containsKey(uid)) {
                // 设置该uid被当前xid持有
                u2x.put(uid, xid);
                // 把该uid添加该xid已经持有的资源列表中
                putIntoList(x2u, xid, uid);
                return null;
            }
            // 否则，表示uid已经被其他xid持有了，添加状态：xid正在等待资源uid
            waitU.put(xid, uid);
            //把当前事务xid添加到正在等待该uid的事务列表中
            putIntoList(wait, uid, xid);
            // 检查是否存在死锁
            if(hasDeadLock()) {
                // 如果检测到死锁，清除等待关系，并抛出死锁异常
                waitU.remove(xid);
                removeFromList(wait, uid, xid);
                throw Error.DeadlockException;
            }
            // 如果没有死锁，为事务创建一个锁
            Lock l = new ReentrantLock();
            l.lock();
            // 锁添加到waitLock映射中，关联事务ID及其等待锁
            waitLock.put(xid, l);
            return l;

        } finally {
            lock.unlock();
        }
    }

    /**
     * 在一个事务 commit 或者 abort 时，就可以释放所有它持有的锁，并将自身从等待图中删除
     */
    public void remove(long xid) {
        lock.lock();
        try {
            List<Long> l = x2u.get(xid);
            if(l != null) {
                while(l.size() > 0) {
                    Long uid = l.remove(0);
                    // 重新分配uid
                    selectNewXID(uid);
                }
            }
            waitU.remove(xid); //移除事务xid的等待记录
            x2u.remove(xid); //移除xid已经获得的资源列表
            waitLock.remove(xid); //移除事务xid的等待锁

        } finally {
            lock.unlock();
        }
    }

    /**
     * 从等待队列中选择一个xid来占用被其他xid释放的uid
     */
    private void selectNewXID(long uid) {
        u2x.remove(uid); //移除当前持有该uid的xid信息
        List<Long> l = wait.get(uid); // 获取正在等待该UID的XID列表
        if(l == null) return; // 表示没有任何事务在等待该资源，直接退出
        assert l.size() > 0;

        while(l.size() > 0) {
            long xid = l.remove(0); //删除列表中第一个等待该uid的事务xid，因为等会要分配给它
            // 判断当前事务xid是否处于等待锁定,如果不是，则该事务可能已被其他资源唤醒或中止，跳过继续处理下一个事务
            if(!waitLock.containsKey(xid)) {
                continue;
            } else {
                u2x.put(uid, xid); // 设置状态： uid被xid持有
                Lock lo = waitLock.remove(xid); //从中waitLock移除xid的锁,并返回锁对象
                waitU.remove(xid); //从waitU中移除xid的等待状态
                lo.unlock(); // 解锁xid的等待锁（lo.unlock()）,让事务继续执行
                break;
            }
        }
        // 如果重新分配uid资源后，等待列表为空，表示没有事务再等待uid，从中wait移除uid的记录。
        if(l.size() == 0) wait.remove(uid);
    }

    private Map<Long, Integer> xidStamp; // 用于记录每个事务的标记状态
    private int stamp; // 时间戳，一个全局变量，用于标记当前死锁检测的搜索路径，每次进行新的死锁检测都会递增

    /**
     * 判断是否存在死锁
     */
    private boolean hasDeadLock() {
        xidStamp = new HashMap<>(); // 初始化标记状态
        stamp = 1; // 初始化时间戳
        // 遍历所有事务
        for(long xid : x2u.keySet()) {
            // 检查该事务是否已被标记
            Integer s = xidStamp.get(xid);
            // s > 0 表示这个事务已经被访问过，并且属于当前或某个已经处理过的连通图，跳过
            if(s != null && s > 0) {
                continue;
            }
            stamp ++; // 为新的DFS分配独立的时间戳
            // 进行深度优先搜索，检测是否存在环
            if(dfs(xid)) {
                // 如果DFS返回true，表示检测到死锁
                return true;
            }
        }
        // 遍历所有事务后未检测到死锁
        return false;
    }


    /**
     * 深度优先搜索
     */
    private boolean dfs(long xid) {
        Integer stp = xidStamp.get(xid); // 获取事务的标记状态
        if(stp != null && stp == stamp) { // 如果当前事务已经被标记为当前时间戳，表示检测到环
            return true;
        }
        if(stp != null && stp < stamp) {  // 如果当前事务属于之前处理的连通图，不检测
            return false;
        }
        xidStamp.put(xid, stamp); // 标记当前事务属于当前时间戳

        Long uid = waitU.get(xid); // 获取事务等待的资源
        if(uid == null) return false; // 如果事务不等待任何资源，返回 false
        Long x = u2x.get(uid); // 获取持有该资源的事务
        assert x != null; // 保证资源一定被持有
        return dfs(x); // 对持有资源的事务递归检测
    }

    /**
     * 将uid1从listMap中uid0对应的列表中移除
     */
    private void removeFromList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        List<Long> l = listMap.get(uid0);
        if(l == null) return;
        Iterator<Long> i = l.iterator();
        while(i.hasNext()) {
            long e = i.next();
            if(e == uid1) {
                i.remove();
                break;
            }
        }
        if(l.size() == 0) {
            listMap.remove(uid0);
        }
    }

    /**
     * 将uid1插入到listMap中uid0对应的列表中
     */
    private void putIntoList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        // 如果listMap中还没有以uid0为key的键值对，则初始化一个键值对
        if(!listMap.containsKey(uid0)) {
            listMap.put(uid0, new ArrayList<>());
        }
        // 获取 uid0 对应的列表，将 uid1 插入到列表的头部，原有元素依次后移，这样可以保证uid1在列表中的优先级最高
        listMap.get(uid0).add(0, uid1);
    }

    /**
     * 判断listMap中是否存在一个键值对，其中键为uid0，值为一个列表List<Long>，并且该列表中是否包含值uid1
     */
    private boolean isInList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        List<Long> l = listMap.get(uid0);
        if(l == null) return false;
        Iterator<Long> i = l.iterator();
        while(i.hasNext()) {
            long e = i.next();
            if(e == uid1) {
                return true;
            }
        }
        return false;
    }

}
